package 数据结构.链表;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-21
 */
public class JZ76删除链表中重复的结点 {
    //直接比较删除
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null || pHead.next == null)
            return pHead;
        ListNode newhead = new ListNode(1);
        newhead.next = pHead;
        ListNode cur = newhead;
        while (cur.next != null && cur.next.next!=null){
            if(cur.next.val == cur.next.next.val){
                int tmp = cur.next.val;
                while (cur.next!=null && cur.next.val == tmp){
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return  newhead.next;
    }


    //哈希表 有序无序均可用
    public ListNode deleteDuplication2(ListNode pHead) {
        //空链表
        if(pHead == null)
            return null;
        Map<Integer,Integer> mp = new HashMap<>();
        ListNode cur = pHead;
        //遍历链表统计每个节点值出现的次数
        while(cur != null){
            if(mp.containsKey(cur.val))
                mp.put(cur.val, (int)mp.get(cur.val) + 1);
            else
                mp.put(cur.val,1);
            cur = cur.next;
        }
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = pHead;
        cur = res;
        //再次遍历链表
        while(cur.next != null){
            //如果节点值计数不为1
            if(mp.get(cur.next.val) != 1)
                //删去该节点
                cur.next = cur.next.next;
            else
                cur = cur.next;
        }
        //去掉表头
        return res.next;
    }

}
